/*
 * @lc app=leetcode.cn id=130 lang=typescript
 *
 * [130] 被围绕的区域
 */

// @lc code=start
/**
 Do not return anything, modify board in-place instead.
 */
function solve(board: string[][]): void {
  const dir = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1],
  ];
  const n = board.length;
  const m = board[0].length;
  // 搜索每一个跟边界上的O相连的O
  const dfs = (i: number, j: number) => {
    board[i][j] = 'o';

    for (let k = 0; k < dir.length; k++) {
      const x = i + dir[k][0];
      const y = j + dir[k][1];
      if (x < 0 || x >= n) continue;
      if (y < 0 || y >= m) continue;
      if (board[x][y] !== 'O') continue;
      dfs(x, y);
    }
    return;
  };

  // 矩阵的第一列和最后列
  for (let i = 0; i < n; i++) {
    if (board[i][0] === 'O') dfs(i, 0);
    if (board[i][m - 1] === 'O') dfs(i, m - 1);
  }
  // 矩阵的第一行和最后行
  for (let j = 0; j < m; j++) {
    if (board[0][j] === 'O') dfs(0, j);
    if (board[n - 1][j] === 'O') dfs(n - 1, j);
  }

  // 将O换成X，o还原
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (board[i][j] === 'O') board[i][j] = 'X';
      if (board[i][j] === 'o') board[i][j] = 'O';
    }
  }

  return;
}
// @lc code=end
